package top100.dfs;

import top100.linklist.Solution234;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/22 11:11
 * @description:
 * 拓扑排序不用区分什么广度优先深度优先把自己弄乱了，抓住节点入度和出度的本质特征。
 * 方法一： 从入度思考(从前往后排序)， 入度为0的节点在拓扑排序中一定排在前面, 然后删除和该节点对应的边, 迭代寻找入度为0的节点。
 * 方法二： 从出度思考(从后往前排序)， 出度为0的节点在拓扑排序中一定排在后面, 然后删除和该节点对应的边, 迭代寻找出度为0的节点。
 */
public class Solution207 {
    List<List<Integer>> edges = new ArrayList<>();
    int[] inDegrees;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        inDegrees = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int next = prerequisites[i][0];
            int pre = prerequisites[i][1];
            edges.get(pre).add(next);
            inDegrees[next]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0 ;i < inDegrees.length;i++){
            if(inDegrees[i]==0){
                q.add(i);
            }
        }
        int count = 0;
        while (!q.isEmpty()){
            int u = q.poll();
            count++;
            for(Integer v : edges.get(u)){
                inDegrees[v]--;
                if(inDegrees[v]==0){
                    q.offer(v);
                }
            }
        }
        return count == numCourses;
    }

    public static void main(String[] args) {
        Solution207 solution = new Solution207();
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};
        System.out.println(solution.canFinish(numCourses, prerequisites));
        numCourses = 2;
        prerequisites = new int[][]{{1, 0}, {0, 1}};
        System.out.println(solution.canFinish(numCourses, prerequisites));
        numCourses = 3;
        prerequisites = new int[][]{{1, 0}, {1, 2}, {0, 1}};
        System.out.println(solution.canFinish(numCourses, prerequisites));
    }
}
